<?php

/**
 * 双链表
 */

/**
 * 节点数据
 */
class Node
{
    public $data;   //节点数据
    public $pre;    //前驱
    public $next;   //后继
    
    public function __construct($data)
    {
        $this->data = $data;
        $this->pre  = NULL;
        $this->next = NULL;
    }
}

class DoubleLinkedList
{
    public  $header;//头节点
    
    /**
     * 初始化
     */
    public function __construct($data)
    {
        $this->header = new Node($data);
    }
    
    /**
     * 查找节点
     *
     * @param string $data 节点数据
     *
     * @return object
     */
    public function find($data)
    {
        $current = $this->header;
        while($current->data != $data)
        {
            $current = $current->next;
        }
        
        return $current;
    }
    
    /**
     * 更新节点
     *
     * @param string $item 当前节点数据
     * @param string $new  更新的节点数据
     *
     * @return boolean
     *
     */
    public function update($item,$new)
    {
        $current = $this->find($item);
        $current->data = $new;
        return true;
    }
    
    /**
     * 查找最后一个节点
     */
    public function findLast()
    {
        $current = $this->header;
        while($current->next != NULL)
        {
            $current = $current->next;
        }
        
        return $current;
    }
    
    /**
     * 在当前节点后插入
     *
     * @param string $item 当前节点
     * @param string $new  插入的新节点
     *
     * @return boolean
     */
    public function insert($item,$new)
    {
        $new_node = new Node($new);
        $current_node = $this->find($item);
        
        $new_node->next     = $current_node->next;
        $new_node->pre      = $current_node;
        $current_node->next = $new_node;
        return true;
    }
    
    /**
     * 删除节点
     *
     * @param string $item 节点数据
     *
     * @return boolean
     */
    public function delete($item)
    {
        $current_node = $this->find($item);
        if ($current_node->next != NULL)
        {
            $current_node->pre->next = $current_node->next;
            $current_node->next->pre = $current_node->pre;
            
            $current_node->next = NULL;
            $current_node->pre  = NULL;
            return true;
        }
    }
    
    /**
     * 显示链表元素
     */
    public function show()
    {
        $current = $this->header;
        while($current->next == NULL)
        {
            echo "这是一个空的链表";
            return;
        }
        
        while($current->next != NULL)
        {
            echo $current->next->data."  ";
            $current = $current->next;
        }
        
        return;
    }
    
    /**
     * 反转链表
     */
    public function reverse()
    {
        $current = $this->findLast();
        while($current->pre != NULL)
        {
            echo $current->data."  ";
            $current = $current->pre;
        }
    }
}

//插入
$double_linked_list = new DoubleLinkedList('header');
$double_linked_list->insert('header','A');
$double_linked_list->insert('A','B');
$double_linked_list->insert('B','C');
$double_linked_list->insert('C','D');
$double_linked_list->insert('D','E');
$double_linked_list->insert('E','F');
$double_linked_list->show();

//更新
echo PHP_EOL;
$double_linked_list->update('C',"G");
$double_linked_list->show();

//反转
echo PHP_EOL;
$double_linked_list->reverse();

//删除
echo PHP_EOL;
$double_linked_list->delete('G');
$double_linked_list->show();


